package 作业基础3;

public class DoublyLinkedList<T> {
    private class Node{
        private T value;
        private Node next;
        private Node prev;
        public Node(T value){
            this.value=value;
            this.next=null;
            this.prev=null;
        }
    }

    private Node head;
    private Node tail;
    public DoublyLinkedList(){
        this.head=null;
        this.tail=null;
    }
    //empty list?
    public boolean Empty(){
        return this.head==null;
    }
    //add to front
    //两种情况:链表为空和正常
    public void PushFront(T key){
        Node node=new Node(key);//node.prev=null;
        node.next=this.head;
        this.head=node;
        if(this.tail==null) this.tail=this.head;//原本无元素的话,需要将尾节点设置为刚插入的新节点
        else this.head.next.prev=node;//原本有元素的话设置原head的prev节点
    }
    //return front item
    public T TopFront(){
        if(Empty()) throw new IndexOutOfBoundsException("linked list is empty");
        return head.value;
    }
    //remove front item
    //两种情况：只有一个元素和正常
    public void PopFront(){
        if(Empty()) return;
        if(this.head!=this.tail) this.head.next.prev=null;//两个元素及以上要设置prev节点
        this.head=this.head.next;
        if(this.head==null) this.tail=null;//只有一个元素,pop后变为空链表
    }
    //add to back
    public void PushBack(T key){
        Node node=new Node(key);
        if(this.tail==null){
            this.head=this.tail=node;
        }
        else{
            this.tail.next=node;
            node.prev=this.tail;
            this.tail=node;
        }
    }
    //return back item
    public T TopBack(){
        if(Empty()) throw new IndexOutOfBoundsException("linked list is empty");
        return tail.value;
    }
    //remove back item
    //拥有prev节点后无须从头遍历
    public void PopBack(){
        if(Empty()) return;
        if(this.head==this.tail) this.head=this.tail=null;
        else{
            this.tail=this.tail.prev;
            this.tail.next=null;
        }
    }
    //is key in list?
    public boolean Find(T key){
        Node node=this.head;
        while(node!=null){
            if(node.value==key) return true;
            node=node.next;
        }
        return false;
    }
    //remove key from list
    public void Erase(T key){
        Node node=this.head;
        while(node!=null){
            if(node.value==key){
                if(this.head==this.tail){
                this.head=this.tail=null;//只有一个元素
                break;
                    }
                else if(node==this.head) {
                    this.head=this.head.next;//删除的是头元素
                    this.head.prev=null;
                }
                else{
                    node.prev.next=node.next;
                    if(node==this.tail) this.tail=node.prev;//如果删除的是尾节点,要改变尾节点
                    else node.next.prev=node.prev; //非尾节点要改变被删节点的下一个节点的prev
                }
            }
            node=node.next;
        }
    }
    //adds keys before node
    //拥有prev节点后不用遍历
    public void AddBefore(Node node, T key){
        Node New=new Node(key);
        if(node==this.head){
            New.next=this.head;
            this.head.prev=New;
            this.head=New;
        }
        else{
            node.prev.next=New;//改变被插入节点前一个节点的next节点
            New.prev=node.prev;//设置插入节点的prev节点
            New.next=node;
            node.prev=New;
        }
    }
    //adds key after node
    public void AddAfter(Node node, T key){
        Node New=new Node(key);
        New.next=node.next;
        New.prev=node;
        node.next=New;
        if(node==this.tail) this.tail=New;//如果插在尾节点后要变更尾节点
        else node.next.prev=New;//插入的不在尾节点后,就需要要改变插入位置后一个节点的prev节点
    }
    //print the value of the whole linked list
    public void Print(){
        Node node=this.head;
        while(node!=null) {
            System.out.print(node.value+" ");
            node=node.next;
        }
        System.out.println();
    }

    public Node getHead(){
        return head;
    }

    public Node getNode(){
        return head.next.next.next;
    }

    public static void main(String[] args){
        DoublyLinkedList<Integer> list= new DoublyLinkedList<>();
        for(int i=5;i>0;i--) list.PushFront(i);//test PushFront
        for(int i=6;i<11;i++) list.PushBack(i);//test PushBackT
        list.Print();
        System.out.println(list.TopFront()+" "+list.TopBack());//test TopFront and TopBack
        list.PopFront();
        list.PopBack();
        list.Print();
        list.AddBefore(list.getHead(),11);
        list.AddBefore(list.getNode(),12);
        list.Print();
        list.AddAfter(list.getHead(),13);
        list.AddAfter(list.getNode(),14);
        list.Print();
        System.out.println(list.Find(22)+" "+list.Find(9));
        list.Erase(11);
        list.Erase(9);
        list.Erase(13);
        list.Print();
    }
}
